package org.example.algorithm.heap;

public class MaxHeap {
    public int[] heap;
    public int capacity;
    public int size;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        heap = new int[capacity];
    }

    public void insert(int value) {
        if (size == capacity) {
            throw new IllegalStateException("heap is full");
        }
        heap[size] = value;
        size++;
        siftUp(size-1);
    }

    public void siftDown(int pos) {
        int leftIndex = 2 * pos + 1;
        int rightIndex = 2 * pos + 2;
        int maxPos = pos;
        if (leftIndex < size && heap[leftIndex] > heap[maxPos]) {
            maxPos = leftIndex;
        }
        if (rightIndex < size && heap[rightIndex] > heap[maxPos]) {
            maxPos = rightIndex;
        }
        if (maxPos != pos) {
           swapHeap(pos, maxPos);
           siftDown(maxPos);
        }
    }

    public void siftUp(int pos) {
        int parentIndex = (pos - 1) / 2;
        if (parentIndex >= 0 && heap[parentIndex] < heap[pos]) {
            swapHeap(pos, parentIndex);
            siftUp(parentIndex);
        }

    }

    public int removeMax() {
        if (size == 0) {
            throw new IllegalStateException("heap is empty");
        }
        int max = heap[0];
        heap[0] = heap[size-1];
        size--;
        siftDown(0);
        return max;
    }

    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("heap is empty");
        }
        return heap[0];
    }

    //交换元素
    private void swapHeap(int from, int to) {
        int temp = heap[from];
        heap[from] = heap[to];
        heap[to] = temp;
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(5);
        maxHeap.insert(8);
        maxHeap.insert(1);
        maxHeap.insert(2);
        maxHeap.insert(3);
        maxHeap.insert(9);
        maxHeap.insert(21);
        int max = maxHeap.peek();
        System.out.println(max);
        maxHeap.removeMax();
        max = maxHeap.peek();
        System.out.println(max);
        for (int i=0;i<maxHeap.size;i++) {
            System.out.println(maxHeap.heap[i]);
        }
    }
}
